package algorithm.first;


import java.util.*;

public class EvaluateDemo {


    public static void main(String[] args) {
        String string = InfixToSuffix("1+2*3");
        double result = EvaluateSuffixExpressions(string);
        System.out.println(result);
    }

    static int getOperatorPriority(String operatorStr) {
        switch (operatorStr) {
            case "+":
            case "-":
                return 0;
            case "*":
            case "/":
                return 1;
            default:
                return -1;
        }
    }

    static String InfixToSuffix(String express) {
        express = express.replace("+", " + ");
        express = express.replace("-", " - ");
        express = express.replace("*", " * ");
        express = express.replace("/", " / ");
        express = express.replace("(", " ( ");
        express = express.replace(")", " ) ");
        List<String> list = new ArrayList();
        Stack<String> stack = new Stack<>();
        String[] expressArray = express.split(" ");
        for (int i = 0; i < expressArray.length; i++) {
            String item = expressArray[i];
            if ("".equals(item)) {
                continue;
            }
            switch (item) {
                case "(":
                    stack.push(item);
                    break;
                case ")": {
                    while (!"(".equals(stack.peek())) {
                        list.add(stack.pop());
                    }
                    stack.pop();
                }
                break;
                case "+":
                case "-":
                case "*":
                case "/": {
                    while (!stack.isEmpty() && getOperatorPriority(item) <= getOperatorPriority(stack.peek())) {
                        list.add(stack.pop());
                    }
                    stack.push(item);
                }
                break;
                default:
                    list.add(item);
            }
        }
        while (!stack.isEmpty()) {
            list.add(stack.pop());
        }
        StringBuilder builder = new StringBuilder();
        for (String item : list) {
            builder.append(item + " ");
        }
        return builder.toString();
    }

    static double EvaluateSuffixExpressions(String SuffixExpressions) {
        String[] array = SuffixExpressions.split(" ");
        Stack<Double> vals = new Stack<>();
        for (int i = 0; i < array.length; i++) {
            String item = array[i];
            double first = 0;
            double second = 0;
            switch (item) {
                case "+":
                    first = vals.pop();
                    second = vals.pop();
                    vals.push(first + second);
                    break;
                case "-":
                    first = vals.pop();
                    second = vals.pop();
                    vals.push(first - second);
                    break;
                case "*":
                    first = vals.pop();
                    second = vals.pop();
                    vals.push(first * second);
                    break;
                case "/":
                    first = vals.pop();
                    second = vals.pop();
                    vals.push(first / second);
                    break;
                default:
                    Double number = Double.valueOf(item);
                    vals.push(number);
            }

        }
        return vals.pop();
    }
}

